With improved display technology, increasing mobile computing and data storage capabilities, the trend exists on increasing the amount of image information shown on physical and virtual displays of smaller and smaller size, such as handheld devices, cell phones, browser windows and thumbnails. Such a display of image information requires reformatting originally stored images, often called repurposing.
Given a scanned document, resizing of the entire document to a target display (hereinafter referred as canvas) by downsampling often results in loss of readability of text and recognizability of image features.
There are many prior art techniques related to reformatting documents and images. These include pagination and formatting, yellow-pages pagination and layout, document summarization, text summarization for handheld devices, web images for handheld devices, and video summarization.
Pagination and formatting are standard parts of every typesetting program. Usually, the initial page space is unlimited and ASCII text and images are placed in a way that semantic orders and relationships between pictures and text references are maintained. For more information, see, for example, The TeXbook, by D. E. Knuth, Addison-Wesley, 1986. The goal is to keep the numbers of pages as small as possible, while including all the available text and all pictures. In one existing method, document objects are rearranged on pages (called tiling), where a user determines which parts to delete, expand or shrink. After that decision has been made up front, an algorithm determines a layout that minimizes the number of pages used. An ordering of text objects is performed with respect to the reading order from the segmentation process, and images are squeezed into this order by checking the closest text object neighbors. For more information, see U.S. Pat. No. 5,553,217, entitled “Document Layout Using Tiling”, issued to Hart et al.
The layout for Yellow-Pages types of documents faces the problem of placing ads near corresponding text sections while using as few pages as possible. The size for text and ads is fixed, and all objects have to be included (e.g., R. Johari, J. Marks, A. Partovi, and S. Shieber, “Automatic Yellow-Pages Pagination and Layout,” Journal of Heuristics, pp. 321–342, 1997).
A representation of pictorial structures is given in M. A. Fischler, R. A. Elschlager “The Representation and Matching of Pictorial Structures,” IEEE Transactions on Computers, vol. C-22, No. 1, January 1973. The authors present a description of an image into a number of components held together by “springs”. The description is used for deriving a metric to measure similarity of images by allowing the springs to stretch and measure the goodness of the component match by the amount of stretching of the springs.
Another document layout includes gemLayout rhetorical structure theory to maintain semantic relationships between text segments (R. Henschel, J. Bateman, J. Delin, “Automatic Genre-Driven Layout Generation,” Proceedings of KONVENS 2002, 6. Konferenz zur Verarbeitung naturlicher Sprache, DKFI, Saarbrucken, 2002.
A layout algorithm for constrained displays allowing user interactivity is LayLab in W. H. Graf, “The Constrained-Based Layout Framework LayLab and Its Applications,” Proceedings of ACM Workshop on Effective Abstractions in Multimedia, Layout and Interaction, San Francisco, Calif., 1995.
The area of document summarization is focused on reflecting semantic importance of the text contained in a document. Approaches using dictionaries and specific language knowledge to determine significance of strings of characters are disclosed in U.S. Pat. No. 5,832,530, entitled Method and Apparatus for Identifying Words Described in a Portable Electronic Document, issued Nov. 3, 1998.
Text summarization for handheld devices is mainly applied to web pages. In O. Buyukkokten, H. Garcia-Molina, and A. Paepcke, “Text Summarization of Web pages on Handheld Devices,” in Proc. of 10th International WWW Conference, Hong Kong, China, 2001, a web page, in a macro-level step, is divided into Semantical Text Units (STU) by using html/xml specific structures. In a second step, a micro-level summarization is performed by displaying a combination of only a limited number of lines, keywords, and the most significant sentence.
Y. Wu and D. Lopresti, “Resource-Optimized Delivery of Web Images to Small-Screen Devices,” in Proceedings of SPIE, 2003, pp. 144–155, discloses preparing images in GIF format for reformatting for display on handheld devices. In the article, the size of the handheld display is fixed. The reformatting technique stores two resolutions of an image, and then performs a color reduction and codes the image in a way that requires little bandwidth for the transmission. The reformatting is done for only one fixed display.
In T. M. Breuel, W. C. Janssen, K. Popat, and H. S. Baird, “Paper to PDA,” in Proceedings of the International Conference on Pattern Recognition (ICPR'02), Quebec City, Quebec, Canada, 2002, scanned documents are reformatted for display on a PDA. This work is focused on text with preservation of the reading order being the first goal.
S. Uchihasi and J. Foote, “Summarizing video using a shot importance measure and a framepacking algorithm,” in Proceedings of ICASSP, 1999, pp. 3041–3044, discloses a method of video summarization that uses a shot importance measure and a packing algorithm for selected key frames. The importance measure selects the key frames and determines the size at which a key frame is to be displayed. The key frames are selected from a temporal sequence. The packing is performed by evaluation of a cost function in an optimization process.
An example of a technology for displaying symbolic documents (HTML documents) on constrained displays is “Opera Small-Screen Rendering.™.”
Some layout problems are related to an optimization problem. First optimization problems will be described, then techniques for solving them will be described. An optimization problem includes an objective function to be maximized or minimized, unknowns (or variables) that effect the value of the objective function, and constraints that limit the allowed values of the unknowns. A solution that satisfies all constraints (without necessarily minimizing or maximizing the objective function) is called a feasible solution. Optimization problems may have multiple objective functions.
For the layout problem, examples of unknowns include position and scale for a particular area. Examples of constraints are that the position of a particular area must be within the canvas and that the scale must be greater than a minimum value. An example objective function is that the amount of the canvas covered by areas should be maximized.
Optimization problems can be classified into continuous and discrete. In a continuous optimization problem, all variables can take on any real value. Scale is an example of a continuous variable. In a discrete optimization problem, at least some of the variables can only have integer values. The decision whether to include an area or not and the relative location of areas (above/same/below, right/same/left) are examples of discrete variables.
Packing problems are applications of optimation problems. In general, objects of specified sizes must be packed into one or more spaces, or containers, etc. of specified size. An equivalent class of problems includes cutting problems where a material of specified size must be cut into objects of specified sizes.
Two-dimensional packing problems are most related to the layout problem. Many problems are formulated using rectangles for objects and spaces and requiring orthogonal placement (or placement/cuts parallel to an edge of the rectangular space). Some problems are limited to “guillotine cuts”, cuts extending from one edge of the space or a previously cut rectangle to another edge.
Pallet loading (or pallettization) is a two dimensional packing problem limited to rectangles and orthogonal placement. In this instance, pallet means a platform for transporting materials, not a set of colors. The goal is to maximize the number of objects that can be packed onto the pallet. This relates to a canvas with fixed width and height.
Two dimensional strip packing and bin-packing are problems also limited to rectangles and orthogonal placement. Both pack a given set of objects. If all the given set of objects are known at the start, the problem is called an off-line problem. If not all of the objects are known initially, the problem is called an on-line problem. Strip packing has a space that is fixed in one dimension and the goal of minimizing the other dimension. It is related to a canvas of fixed width and variable height. Bin-packing uses fixed size spaces (bins) and has the goal of minimizing the number of bins. Bin-packing with more than one bin is related to a layout problem with more than one canvas. In a computer job scheduling problem, one dimension (the fixed dimension for strip packing) can be memory required or other requirements and the other dimension can be time. In a VLSI test scheduling problem, one dimension (the fixed dimension for strip packing) can be the wires required or test vector size for a test and the other dimension can be time (see Vikram Iyengar, Krishnendu Chakrabarty and Erik Jan Marinissen, “On Using Rectangle Packing for SOC Wrapper/TAM Co-Optimization.”
One-dimensional problems include the classical knapsack problem and one-dimensional bin-packing, where a two-dimensional knapsack problem is another name for a two-dimensional packing problem. Loading problems can be one dimensional or multi-dimensional with independent dimensions such as weight and capacity. Three-dimensional packing problems include container stuffing and pallet loading for objects that cannot be efficiently packed in layers.
The facility layout problem is a type of packing problem. See, Russell D. Meller and Kai-Tin Gau, “The Facility Layout Problem: Recent and Emerging Trends and Perspectives,” Journal of Manufacturing Systems, Vol,. 15/No. 5 1996. Typically, the “objects” to be packed are departments (of unequal area) and they must be packed into facility such as a building. The goal is to minimize the material handling cost inside the building (or minimize the traffic between departments). Typically, the area of each object is fixed, but the width and length can vary within some range (i.e., the aspect ratio of the object can vary). (Reflow of text also similarly has approximately fixed area but variable width and length.) The block layout which specifies the relative location of each department is more relevant to the layout problem than the detailed layout which specifies aisle structures, input/output points, etc. Relative position can be a constraint. VLSI floorplanning and VSLI macro-cell layout are closely related to facility layout. Location problems include both facility layout and facility location (which ignore geometric constraints).
Now that optimization problems have been described above, techniques for solving are as follows.
Discrete optimization problems can be solved by exhaustive search when the number of possible values for all variables is small. For larger problems that can be decomposed into independent sub-problems, dynamic programming can be used.
Larger problems can be handled by branch-and-bound methodology. Branch-and-bound requires that all possible values for all variables be sorted into a tree structure. At leaf nodes, an exact value for the objective function can be computed. At non-leaf nodes, a bound for the best case value of the objective function for all leaf-nodes that are in this non-leaf node's sub-tree can be computed. If the bound is worse than the current best solution, then all the possible variable values associated with this sub-tree can be ignored. The ordering of the tree structure is an important heuristic. If a good ordering and good bounds can be found for a particular problem, then the number of possibilities considered by branch-and-bound is much less than for exhaustive search.
Another technique for solving discrete optimization problems is to first relax the integer constraint and find the best continuous valued solution and then search only the closest integer solutions. Relaxation can be effective if the number of integer choices is large. Relaxation can also be used to find bounds in a branch-and-bound solution.
Continuous problems with linear constraints and a linear objective function can be solved with the simplex method or the interior-point methods. For non-linear objective functions, other techniques, such as quadratic programming which uses a quadratic approximation for the objective function may be used. See, Nicholas I. M. Gould and Philippe L. Toint, “A Quadratic Programming Bibliography.” Convex problems can be solved by interior-point methods.
Solutions for a number of packing problems are summarized in Kathryn A. Dowsland and William B. Dowsland, “Packing Problems,” European Journal of Operational Research, 56 (1002) 2–14, North-Holland. For strip packing, two simple algorithms are “level” and “shelf”. Consider the width to fixed and height to be minimized. The “level” algorithm divides the space into rows with height equal to the first object placed in that row. “Level” is particularly appropriate when the object are sorted into decreasing height order. The “shelf” algorithm uses rows of height chosen out of a set of predetermined heights. “Shelf” can used when sorting is not possible. “Level” and “shelf” produce packing that are guillotineable and also further limited in that the packing can be obtained by first making horizontal guillotine cuts and then making vertical guillotine cuts. Such algorithms are sometimes referred to as 1.5 dimensional.
The “Level” algorithm used to solve packing problems is depicted in FIG. 1. Referring to FIG. 1, objects to be packed are sorted by height. The sorted objects would be packed in order into the strip. The first row 110 in the strip has a height equal to the first object 115 packed into the first row 110. When the first row 110 is filled with objects, the next object 125 in order is packed into a second row 120 with height equal to the next object 125. When the second row 120 is filled with objects, the next object 135 in order is packed into a third row 130 with a height equal to the next object 135. Then the third row 130 is filled with objects. The height of the strip is the sum of the heights of rows 110, 120 and 130. It should be noted that objects are rigid and may not undergo geometric manipulations such as scaling or cropping. Furthermore, the relative position of objects is arbitrary.
Bin packing problems can be solved by first solving a strip packing problem and then treating the fitting of each row into an appropriate bin as a one-dimensional problem.
There are two traditional approaches for exact solutions to facilities layout problems (see Russell D. Meller and Kai-Tin Gau, “The Facility Layout Problem: Recent and Emerging Trends and Perspectives,” Journal of Manufacturing Systems, Vol. 15/No. 5 1996). One way is to model the problem as a quadratic assignment problem (QAP) and to solve the QAP with a branch-and-bound approach. A second way is to use a graph-theoretic approach. For this approach, the desirability of locating each pair of objects adjacent to each other is assumed to be known. Graph-theoretic approaches have multiple steps: the initial step considers if objects are adjacent and ignores area and shape while the final step produces a block layout meeting all constraints.
Heuristic solutions to facilities layout problems are often used because of the complexity of exact solution (see Russell D. Meller and Kai-Tin Gau, “The Facility Layout Problem: Recent and Emerging Trends and Perspectives,” Journal of Manufacturing Systems, Vol. 15/No. 5 1996). CRAFT uses two-way or three-way exchanges chosen with steepest decent to improve an initial layout. LOGIC improves an initial layout based on a data structure that specifies whether objects are to the left, right, above, or below each other and does two-way exchanges of these relationships. FLEX-BAY is related to strip packing. Recent work includes Miguel F. Anjos, Anthony Vannelli, “A New Mathematical Programming Framework for Facility Layout Design”, University of Waterloo Technical Report UW-W&CE#2002–4.